package dp.路径;

import java.util.HashMap;
import java.util.Map;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 打家劫舍iii337.java
 * @createTime 2024年03月27日 09:49:00
 */
public class 打家劫舍iii337 {
	/*
		状态：位置
		定义dp[i]表示当前位置的可抢到的最大金额
		如果根节点不抢,就抢左和右子节点
		如果根节点抢，就抢左或者右字节的所有子节点
		边界：根节点不存在为0
		*/
	Map<TreeNode, Integer> nodeValue = new HashMap<>();

	public int rob(TreeNode root) {
		if (root == null) {
			return 0;
		}
		if (nodeValue.containsKey(root)) {
			return nodeValue.get(root);
		}
		//根节点不抢
		int noRootValue = rob(root.left) + rob(root.right);
		//根节点抢
		int rootVaule = root.val + (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right)) +
				(root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));
		nodeValue.put(root, Math.max(noRootValue, rootVaule));
		return nodeValue.get(root);
	}
	public  class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {}

		TreeNode(int val) {this.val = val;}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

}

